#include <iostream>
#include <vector>
using namespace std;

/* @brief 求一个子序列的和
 *
 * @param arr: 数组指针
 * @param head: 子序列起始元素下标
 * @param tail: 子序列最后元素下标
 *
 */
int sum_of_seq(int* arr, int head, int tail) {
  int sum = 0;
  for (int i = head; i <= tail; i++) {
    sum += arr[i];
  }
  return sum;
}

/* @brief 求最大子序列的和(暴力遍历)
 *  外面两层循环，中间求和需要遍历一次，复杂度 O(n^3)
 *
 * @param arr: 数组指针
 * @param head: 数组起始元素下标
 * @param tail: 数组最后元素下标
 *
 */
int max_subseq_bf(int* arr, int head, int tail) {
  int ans = 0;
  for (int i = head; i <= tail; i++) {
    for (int j = i; j <= tail; j++) {
      int sum = sum_of_seq(arr, i, j);
      if (sum > ans) ans = sum;
    }
  }
  return ans;
}

/* @brief 求最大子序列的和(动态规划)
 *
 *  动态规划求解，只需要一层循环O(n) dp[i] 保存以i结尾的最大子序列和
 *
 * @param arr: 数组指针
 * @param head: 数组起始元素下标
 * @param tail: 数组最后元素下标
 *
 */
int max_subseq_dp(int* arr, int head, int tail) {
  int ans = 0;
  vector<int> dp(tail - head + 2);
  for (int i = head; i <= tail; i++) {
    if (dp[i] > 0) {
      dp[i + 1] = dp[i] + arr[i];
    } else {
      dp[i + 1] = arr[i];
    }
    if (dp[i + 1] > ans) ans = dp[i + 1];
  }
  return ans;
}

int main(int argc, char** argv) {
  int arr[] = {1, -2, 3, -4, 5, -6};
  cout << max_subseq_dp(arr, 0, sizeof(arr) / sizeof(int) - 1) << endl;
  int arr2[] = {1, 2, 3, 4, 5, 6};
  cout << max_subseq_dp(arr2, 0, sizeof(arr2) / sizeof(int) - 1) << endl;
}